package sort;

//折半插入排序,在原插入排序的基础之上不是一个个查找，而是采用二分查找
//todo
public class HalfInsertSort {

	public static void main(String[] args) {
		int[] a = { 5, 2, 9, 3, 10, 1, 15, 2, 6, 7, 19, 50, 69, 100, 150, 160,
				132, 169 };
		for (int i : a) {
			System.out.print(i + " ");
		}
		sort(a);
	}

	public static void sort(int[] a) {
		int i, j;
		System.out.println();
		// 首先将最小的元素放到数组中的第一个元素
		for (i = a.length - 1; i >= 1; i--) {
			if (a[i] < a[i - 1]) {
				int temp = a[i - 1];
				a[i - 1] = a[i];
				a[i] = temp;
			}
		}
		// 对元素进行插入排序
		for (i = 2; i < a.length; i++) {
			// 用j将i的值存储起来
			j = i;
			int temp = a[i]; // 存储a[i]的值
			while (temp < a[j - 1]) {
				a[j] = a[j - 1];
				j--;
			}
			a[j] = temp;// 当直到a[i]的值比a[j-1]要大，则a[j]的值就是a[i]的值
		}
		for (int k : a) {
			System.out.print(k + " ");
		}
	}
}
